package csxx;

public class CityInformation {
    public Node head;

    public CityInformation() {
        this.head = new Node();//调用结点初始化中的无参构造函数完成对头结点的建立
    }

    // 尾插法
    public void create1(Object[] temp, int[] time) throws Exception {
        Node rear = this.head;    //尾指针rear
        if (temp == null)
            throw new Exception("空对象异常");
        if (temp.length == 0)
            System.out.println("链表为空");
        for (int i = 0; i < temp.length; i++) {
            rear.next = new Node(temp[i],time[i], null);
            rear = rear.next;        //尾指针自赋值，指向新的尾结点
        }
    }


    //将一个已经存在的带头结点单链表制成空表
    public void clear() {
        head.data = null;
        head.next = null;
        head.hour = 0;
    }

    // 判断带头结点的单链表是否为空
    public boolean isEmpty() {
        return head.next == null;
    }

    // 求带头结点的单链表的长度
    public int length() {
        Node p = head.next;                 //初始化，p指向首结点，length为计数器
        int length = 0;
        while (p != null) {                   //从首结点开始向后查找，直到p为空
            p = p.next;                     //指向后继结点
            ++length;                       //长度增1
        }
        return length;
    }

    //按值查找
    public int search(Object key) throws Exception {
        if (key == null)
            throw new Exception("需要寻找城市不存在");
        int i = -1;
        for (Node p = this.head.next; p != null; p = p.next) {        //p这里指向头结点，不是首结点；p自赋值
            i++;
            if (p.data.equals(key))                                  //p指向结点的数据域与需要寻找元素进行对比
                return i;                                           //返回位置
        }
        throw new Exception("没有该城市");
    }


    // 在带头结点的单链表中的第i个结点之前插入一个值为x的新节点
    public void insert(int i, int t,Object x) throws Exception {
        if (x == null)
            throw new Exception("不能插入空对象");
        Node p = this.head;                                //p指向头结点
        for (int j = 0; p.next != null && j < i; j++)    // 寻找插入位置
            p = p.next;
        p.next = new Node(x,t, p.next);
    }

    //在单链表中插入一个值为x的新结点
    public void insert2(Object y,int t) throws Exception {
        if (y == null)
            throw new Exception("不能插入空对象");
        Node p = this.head;
        while (p.next != null) {
            p = p.next;
        }
        p.next=new Node(y,t,p.next);
    }


    // 删除带头结点的单链表中的第i个结点
    public Object remove(int i) throws Exception {
        if (i >= 0 && i < length()) {
            Node p = this.head;                 //p目前为头指针
            //定位到待删除结点(i)的前驱结点(i - 1)
            for (int j = 0; p.next != null && j < i; j++) {
                p = p.next;
            }
            if (p.next != null) {
                Object old = p.next.data;//获取原对象
                p.next = p.next.next;//删除p的后继结点
                return old;
            }
        }
        //当i < 0或大于表长时
        return null;
    }

    // 在带头结点的单链表中查找值为x的结点
    public int indexOf(Object x) {
        Node p = head.next;                             //初始化，p指向首结点，j为计数器
        int j = 0;
        // 下面从单链表中的首结点开始查找，直到p.data为x或到达单链表的表尾
        while (p != null && !p.data.equals(x)) {
            p = p.next;                                 //指向下一个结点
            ++j;                                        //计数器+1
        }
        if (p != null)
            return j;                                   //返回值为x的结点在单链表中的位置
        else
            return -1;                                  //值为x的结点不在单链表中，则返回-1
    }

    // 输出单链表中的所有结点
    public void display() {
        Node node = head.next;                          //取出带头结点的单链表中的首结点
        while (node != null) {
            System.out.print(node.data + " " + node.hour + " ");        //输出结点的值
            node = node.next;                           //取下一个结点
        }
        System.out.println();                           //换行
    }
}


